#coding:utf-8

from typing import List

class Solution:
    def dfs(self,candidates: List[int], target: int,
        tmp:List[int],ans:List[List[int]],ix:int) ->None:
        if ix == len(candidates):
            return
        if target == 0:
            ans.append(list(tmp))
            return
        
        # 跳过当前
        self.dfs(candidates,target,tmp,ans,ix+1)

        if target-candidates[ix] >= 0:
            tmp.append(candidates[ix])
            self.dfs(candidates,target-candidates[ix],tmp,ans,ix)
            tmp.pop()


    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        # tmp表示已经加到组合里面的
        tmp = []
        self.dfs(candidates,target,tmp,ans,0)
        return ans



if __name__ == "__main__":
    solu = Solution()
    print(solu.combinationSum([2,3,6,7],7))